96

task is quadratically complex, taking 100 time units for 10 nucleotides and 10,000 time

units for 100 nucleotides. Therefore, RNA folds are only calculated for molecules that are

not too large, and database searches are usually not fast for complete molecule folds.

Many computational tasks, e.g. the sequence comparison of protein sequences in the

genome, i.e. again each protein with every other protein, are typically quadratic in their

time requirements. The same applies to pairwise calculations of phylogenetic trees with

phylogenetic software, such as when one calculates a sequence alignment with CLUSTAL

and associated phylogenetic trees with the Neighbor-Joining method.

Many database searches here again require a quadratic or cubic amount of time (sifting

through 10 times more data requires 1000 times more time).

Non-deterministic Polynomial Complexity (NP-Problems)

The case is quite different when the problem becomes many times more difficult with each

step. These are problems that grow exponentially, for example (complexity EXP). The

complexity class NP is now the set of all problems solvable by nondeterministic Turing

machines in polynomial time. Put simply: All problems solvable in polynomial time by a

computer that can randomly select multiple computational paths. This subset of EXP con­

tains a very large number of relevant problems. Since the problems from P can be solved

non-deterministically in polynomial time if they must, P is a subset of NP. These NP-hard

problems are very hard to estimate in computational time. It is true that if the solution is

correct (given by a good fairy, for example), one can check it in polynomial time to see if

it is correct. But from this one does not find it fast or at all without the good fairy.

The best-known problem is the travelling salesman problem (“TSP”), who wants to

visit many cities with an optimally short route on his way. One can only be really sure after

quite long calculations, but these become more than 100 times more complex with each

additional city, for example, with the 200th city even more than 200 times more difficult

with each additional city.

­

1971

1973

1971

­

1973

­

­

8  When Does the Computer Stop Calculating?